//
// Created by REEJI2219 on 2024-09-24.
//
#include <iostream>
using namespace std;
class Sort {
public:
    /**
     *重要步骤
     *1、遍历每一行
     * 插入排序 从小到大
     * @param array
     * @param len
     * @return
     */
    int* insertSort(int* array,int len) {
        //遍历每一列
        for(int i=1;i<len;i++) {
            //要比较的元素，先提前存储
            int key = array[i];
            //空位置，用于后续赋值处理
            int temp=-1;
            //从后向前遍历每一个元素
            for (int j=i-1;j>=0;j--) {
                //大的移动到右边
                if(array[j]>key) {
                    array[j+1]=array[j];
                    //记录空的位置
                    temp=j;
                }else {
                    break;
                }
            }
            //发生过移动，才进行转换赋值，如果temp为-1，说明没有发生过移动，本身数据就在最后
            if(temp!=-1) {
                array[temp]=key;
            }
        }
        print(array,len);
    }

    int* insertSort1(int* array,int len) {
        int i,j;
        //遍历每一列
        for(i=1;i<len;i++) {
            //要比较的元素，先提前存储
            int key = array[i];
            //从后向前遍历每一个元素
            for (j=i-1;j>=0;j--) {
                //大的移动到右边
                if(array[j]>key) {
                    array[j+1]=array[j];
                }else {
                    break;
                }
            }
            array[j+1]=key;
        }
        print(array,len);
    }

    /**
     * 希尔排序
     * @param array
     * @param len
     * @return
     */
    void xeSort(int* array,int len) {
        //分组 每层数据为 8/4 8/2 8/1
        int levelCount = len;
        //循环多少层
        do {
            levelCount=levelCount/2;
            //同一层，每个分开
            for(int broke=0;broke<levelCount;broke++) {
                //每一块的数量,如果8个元素，将被分成4块，每块两个元素
                int eachBrokeSize = len/levelCount;
                //每一块做插入排序，
                for(int i=0;i<eachBrokeSize;i++) {
                    int key = array[i*levelCount+broke];
                    int temp=-1;
                    for (int j=i-1;j>=0;j--) {
                        if(array[j*levelCount+broke]>key) {
                            array[(j+1)*levelCount+broke]=array[j*levelCount+broke];
                            temp=j*levelCount+broke;
                        }
                    }
                    if(temp!=-1) {
                        array[temp]=key;
                    }
                }
            }
            printf("current_level_count %d :",levelCount);
            print(array,len);
        }while (levelCount>1);
        print(array,len);
    }

    /**
     * 大顶堆构建 每个非叶子节点都进行节点调整
     * @param array d
     * @param n
     */
    void deapBuild(int* array,int n) {
        int len = n/2;
        for(int i=len;i>=0;i--) {
            adjustDownLarge(array,n,i);
        }
        print(array,n);
    }

    /**
     * 1、构建大顶堆
     * 2、将堆顶元素与最后一个节点（已交换节点不再参与）进行交换
     * 3、对根节点进行堆节点调整
     * @param array
     * @param n
     */
    void deapSort(int* array,int n) {
        deapBuild(array,n);
        for(int traget=n-1;traget>0;traget--) {
            swap(array,0,traget);
            adjustDownLarge(array,traget,0);
            print(array,n);
        }
        print(array,n);
    }
    /**
     * 单个大顶堆构建过程
     * @param array
     * @param n
     * @param parent
     */
    void adjustDownLarge(int* array,int n,int parent) {
        //默认第一个是左孩子
        int chlid = parent*2+1;
        while (chlid<n) {//堆调整完标识，就是不存在子节点了
            //左边孩子小于右边孩子，用的孩子跟parent进行比较
            if(chlid+1<n && array[chlid]<array[chlid+1]) {
                chlid=chlid+1;
            }
            //孩子大于父亲，需要进行交换，然后重新向下构建
            if(array[chlid]>array[parent]) {
                //孩子与父亲元素互换
                swap(array,parent,chlid);
                //交换以后可能破坏儿子大顶堆特性，需要向下提调整
                //父亲角标与儿子脚本交换
                parent=chlid;
                //儿子变为孙子
                chlid=parent*2+1;
            }else {
                break;
            }
        }
    }
    void swap(int* array,int source,int target) {
        int temp = array[source];
        array[source]=array[target];
        array[target]=temp;
    }

    /**
     * 冒泡排序 从低到高
     * @param array
     * @param len 
     */
    void bubbleSort(int* array,int len) {
        for (int i=1;i<len;i++) {
            bool sorted = true;
            for (int j=0;j<len-i;j++) {
                //前面比后面大
                if(array[j]>array[j+1]) {
                    //前后交换
                    int temp = array[j+1];
                    array[j+1] = array[j];
                    array[j]=temp;
                    sorted=false;
                }
            }
            if(sorted) {
                printf("has broke %d:\n",i);
                break;
            }
        }
        print(array,len);
    }
    void print(int* array,int len) {
        for(int i=0;i<len;i++) {
            printf("%d ",array[i]);
        }
        printf("\n");
    }

    /**
     * 快速排序
     * @param array
     * @param start
     * @param end
     */
    void quickSort(int *array,int start,int end) {
        if(start<end) {
            //对start，end进行比较交换一次数据
            int position = pattion(array,start,end);
            //左右两侧再进行排序
            quickSort(array,start,position-1);
            quickSort(array,position+1,end);
        }

    }
    int pattion(int *array,int start,int end) {
        //提前拿来，strat被空出来了，可以被直接赋值
        int key = array[start];
        //开始小于结束
        while (start<end) {
            //找到一个右侧比key小的值进行交换
            while (start<end&key<array[end]) {
                end--;
            }
            array[start]=array[end];
            //找到一个比key到的值，进行交换
            while (start<end&array[start]<key) {
                start++;
            }
            array[end]=array[start];
        }
        //此时start=end,此处值被空出来，直接赋值
        array[start]=key;
        return start;
    }

    /**
     * 简单排序
     * @param array
     * @param len
     */
    void sampleSort(int* array,int len) {
        for(int i=0;i<len;i++) {
            int minIndex = i;
            for(int j=i+1;j<len;j++) {
                if(array[j]<array[minIndex]) {
                    minIndex=j;
                }
            }
            int temp = array[i];
            array[i]=array[minIndex];
            array[minIndex]=temp;
        }
        print(array,len);
    }

    /**
     * 归并排序
     * 构建归并树，先分拆，再归并
     * @param array_source 原始数组
     * @param array_temp 临时数组
     * @param start 开始位置
     * @param end 结束位置
     */
    void margeSort(int *array_source,int *array_temp,int start,int end) {
        if (start<end) {
            int mind = (start+end)/2;
            printf("start:%d mind:%d end:%d \n",start,mind,end);
            margeSort(array_source,array_temp,start,mind);
            margeSort(array_source,array_temp,mind+1,end);
            marge(array_source,array_temp,start,end);
        }
    }

    /**
     * 合并排序 前提是两个有序的数组拼接到一块
     * @param array_source 原始数组
     * @param array_temp 临时数组
     * @param start 开始位置
     * @param end 结束位置
     */
    void marge(int *array_source,int *array_temp,int start,int end) {
        //源数据copy数据到辅助数组
        for(int i=start;i<=end;i++) {
            array_temp[i]=array_source[i];
        }
        //开始进行归并
        int k=start;
        int lowIndex = start;
        int mind = (start+end)/2;
        int lowEnd=mind;
        int higIndex=mind+1;
        int higEnd=end;
        //hight low 都没结束，全部比较
        while (k<=end && lowIndex<=lowEnd && higIndex<=higEnd) {
            //从low，hight选取最小值
            if(array_temp[lowIndex]<=array_temp[higIndex]) {
                array_source[k]=array_temp[lowIndex];
                lowIndex++;
            }else {
                array_source[k]=array_temp[higIndex];
                higIndex++;
            }
            k++;
        }
        while (k<=end && lowIndex<=lowEnd) {
            array_source[k]=array_temp[lowIndex];
            lowIndex++;
            k++;
        }
        while (k<=end && higIndex<=higEnd) {
            array_source[k]=array_temp[higIndex];
            higIndex++;
            k++;
        }
    }

    /**
     * 基数排序 也可以叫桶排序
     * 比如对 100~999之间的数据进行排序
     * d为维度 ，个、十、百为三维
     * r为每个维度的桶数量，比如个位有十个数字，十位有十个数字，百位有十个数字。则时间复杂度为 n*d
     * 收集次序决定了排列顺序，从小到大收集，大的在后面，为正序，从大到小收集，小的在后面，为倒序
     * 比如对 100000个学生，按照年月日排序
     * 则有三维
     */
    void blockSort() {

    }
};

// int main(int argc, char *argv[]) {
//     //1 3 4 5 6 7 8 9
//     Sort *sort = new Sort();
//     int array[] = {8,1,3,6,5,4,7,9};
//     sort->insertSort1(array,8);
//     // sort->xeSort(array,8);
//     // sort->bubbleSort(array,8);
//     // sort->quickSort(array,0,7);
//     // sort->print(array,8);
//     // sort->sampleSort(array,8);
//     // int array[] = {53,17,78,9,45,65,87,32};
//     // sort->deapSort(array,8);
//     // int array[] = {2,8,13,15,5,7,12,18};
//     // int *tem_arragy = new int[8];
//     // sort->margeSort(array,tem_arragy,0,7);
//     // sort->print(array,8);
// }
